/*
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的.
*/

package LC0021;

// listnode是一种数据结构
// 存储了当前结点的值，和指向下一个结点的指针
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    // 如何给指针添加结点
    public void add(int num){
        ListNode list = new ListNode(num);

        if(this.next == null) {
            this.next = list;
        } else {
            this.next.add(num);
        }
    }

    public void print(){
        System.out.print(this.val);
        if (this.next != null) {
            System.out.print(",");
            this.next.print();
        }
    }
}

// 递归
    // 递归函数必须要有终止条件，否则会出错；
    // 递归函数先不断调用自身，直到遇到终止条件后进行回溯，最终返回答案。
class Solution1 {
    public static void main(String[] args) {
        Solution1 test = new Solution1();

        ListNode list1 = new ListNode(1);
        list1.add(2);
        list1.add(7);

        ListNode list2 = new ListNode(2);
        list2.add(4);
        list2.add(10);

        test.mergeTwoLists(list1, list2).print();
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null){
            return list2;
        } else if(list2 == null){
            return list1;
            // TODO 如果两个链表都为空? 怎么办?
                // 还是会返回null
        } else if (list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}
// TODO 时间复杂度?
    // O(T) = 递归的数量 * 计算的时间复杂度
// TODO 空间复杂度
    // 当它遇到终止条件准备回溯时，已经递归调用了 m+nm+n 次，使用了 m+nm+n 个栈帧，故最后的空间复杂度为 {\mathcal{O}}(m + n)O(m+n)
